# -*- coding: utf-8 -*-
# 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组
# 注意：答案中不可以包含重复的三元组
# 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]
# 满足要求的三元组集合为：
# [
#   [-1, 0, 1],
#   [-1, -1, 2]
# ]

# # 笨方法
# class Solution(object):
#     def threeSum(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         rtn = [];
#         for i in xrange(0, len(nums)):
#             for j in xrange(i + 1, len(nums)):
#                 for k in xrange(j + 1,len(nums)):
#                     if nums[i] + nums[j] + nums[k] == 0:
#                         rtn.append([nums[i], nums[j], nums[k]]);
#                         break;

#         # 去重
#         # 错误去重方案1：
#         # 思路:
#         # 决定3个未知数需要3个3元1次方程，因已经给出一个，所以再记录2个，比较剩余2个方程即可确认是否是3个相同的数字
#         # 思路误区:
#         # 随人3个3元一次方程可以决定3个数字，但是3个数字的顺序不同时同一个方程的答案可能不一样
#         # eg: [-1, 1]
#         # x + y = 0
#         # x - y = 2 | -2

#         # identify = [];
#         # temp = [];
#         # for i in xrange(0,len(rtn)):
#         #     v1 = rtn[i][0] - rtn[i][1] + rtn[i][2];
#         #     v2 = rtn[i][0] + rtn[i][1] - rtn[i][2];
#         #     j = -1;
#         #     for j in xrange(0, len(identify)):
#         #         if (identify[j][0] == v1 and identify[j][1] == v2) or (identify[j][0] == v2 and identify[j][1] == v1):
#         #             break;
#         #     if j != len(identify) - 1:
#         #         continue;
#         #     print [j, identify, rtn[i], [v1, v2]];
#         #     identify.append([v1, v2]);
#         #     temp.append(rtn[i]);
#         # rtn = temp;

#         return rtn;

# # 笨方法
# # 超出时间限制，想办法优化解答
# class Solution(object):
#     def threeSum(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         rtn = [];
#         for i in xrange(0, len(nums)):
#             for j in xrange(i + 1, len(nums)):
#                 for k in xrange(j + 1,len(nums)):
#                     if nums[i] + nums[j] + nums[k] == 0:
#                         rtn.append([nums[i], nums[j], nums[k]]);
#                         break;

#         unique_rtn = [];
#         is_already_has_all_zero = False;
#         for x in xrange(0, len(rtn)):
#             if rtn[x][0] == 0 and rtn[x][1] == 0 and rtn[x][2] == 0:
#                 if is_already_has_all_zero:
#                     continue;
#                 else:
#                     is_already_has_all_zero = True;
#                     unique_rtn.append(rtn[x]);
#                     continue;

#             is_jump = False;
#             for y in xrange(0, len(unique_rtn)):
#                 if rtn[x][0] in unique_rtn[y] and rtn[x][1] in unique_rtn[y] and rtn[x][2] in unique_rtn[y]:
#                     is_jump = True;
#                     break;
#             if is_jump:
#                 continue;
#             unique_rtn.append(rtn[x]);

#         print len(unique_rtn);
#         return unique_rtn;

# #利用hash_map 仍然超出时间限制
# class Solution(object):
#     def threeSum(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         hash_map = {};
#         for i in xrange(0, len(nums)):
#             if hash_map.has_key(nums[i]):
#                 hash_map[nums[i]] += 1;
#             else:
#                 hash_map[nums[i]] = 1;

#         rtn_dic_list = [];
#         hash_map_keys = hash_map.keys();
#         for i in xrange(0, len(hash_map_keys)):
#             v1_key = hash_map_keys[i];
#             hash_map[v1_key] -= 1;

#             j_begin = 0;
#             if hash_map[v1_key] > 0:
#                 j_begin = i;
#             else:
#                 j_begin = i + 1;

#             for j in xrange(j_begin, len(hash_map_keys)):
#                 v2_key = hash_map_keys[j];
#                 hash_map[v2_key] -= 1;

#                 to_find_key = - v1_key - v2_key;
#                 if hash_map.has_key(to_find_key) and hash_map[to_find_key] > 0:
#                     temp = {};
#                     temp[v1_key] = 1;
#                     if temp.has_key(v2_key):
#                         temp[v2_key] += 1;
#                     else:
#                         temp[v2_key] = 1;
#                     if temp.has_key(to_find_key):
#                         temp[to_find_key] += 1;
#                     else:
#                         temp[to_find_key] = 1;
#                     rtn_dic_list.append(temp);

#                 hash_map[v2_key] += 1;
#             del hash_map[v1_key];

#         unique_rtn_dic_list = [];
#         for i in xrange(0, len(rtn_dic_list)):
#             if rtn_dic_list[i] in unique_rtn_dic_list:
#                 continue;
#             unique_rtn_dic_list.append(rtn_dic_list[i]);

#         rtn = [];
#         for i in xrange(0, len(unique_rtn_dic_list)):
#             temp = [];
#             temp_dic = unique_rtn_dic_list[i];
#             temp_dic_keys = temp_dic.keys();
#             for key in temp_dic_keys:
#                 for j in xrange(0, temp_dic[key]):
#                     temp.append(key);
#             rtn.append(temp);

#         # print len(rtn);
#         return rtn;


# #通过了 嘻嘻！！
# class Solution(object):
#     def threeSum(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         hash_map = {};
#         for i in xrange(0, len(nums)):
#             if hash_map.has_key(nums[i]):
#                 hash_map[nums[i]] += 1;
#             else:
#                 hash_map[nums[i]] = 1;

#         rtn = [];
#         hash_map_keys = hash_map.keys();
#         for i in xrange(0, len(hash_map_keys)):
#             v1_key = hash_map_keys[i];
#             hash_map[v1_key] -= 1;

#             j_begin = 0;
#             if hash_map[v1_key] > 0:
#                 j_begin = i;
#             else:
#                 j_begin = i + 1;

#             already_use_v2_key = [];
#             for j in xrange(j_begin, len(hash_map_keys)):
#                 v2_key = hash_map_keys[j];
#                 hash_map[v2_key] -= 1;

#                 to_find_key = - v1_key - v2_key;
#                 if to_find_key in already_use_v2_key:
#                     hash_map[v2_key] += 1;
#                     continue;

#                 if hash_map.has_key(to_find_key) and hash_map[to_find_key] > 0:
#                     already_use_v2_key.append(v2_key);
#                     rtn.append([v1_key, v2_key, to_find_key]);

#                 hash_map[v2_key] += 1;
#             del hash_map[v1_key];
#         return rtn;







# 阅读评论后发现有不使用hash_map的n平方时间复杂度的解法
# 具体思路是 排序，然后确定一个使用双指针左右查找另外2个
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort();
        rtn = [];
        i = 0;
        while i < len(nums):
            l = i + 1;
            r = len(nums) - 1;
            while l < r:
                sum_3 = nums[i] + nums[l] + nums[r];
                if sum_3 == 0:
                    rtn.append([nums[i], nums[l], nums[r]]);
                    while l < r and nums[l] == nums[l + 1]:
                        print nums[i];
                        l += 1;
                    l += 1;
                elif sum_3 > 0:
                    r -= 1;
                else:
                    l += 1;
            while i < len(nums) - 1 and nums[i] == nums[i + 1]:
                i += 1;
            i += 1;
        return rtn;

t = Solution();
print t.threeSum([-1, 0, 1, 2, -1, -4]);